This invention relates to wireless telecommunication and in particular to wireless mobile Internet digital data communication.
It is well known that the performance of Internet transport and application protocols depends heavily on the characteristics of the underlying network links, and in particular, the bottleneck link. Apart from the impact of competing traffics, a bottleneck link has three primary parameters, namely link bandwidth, buffer size, and queue length. Referring to citations listed below by the bracketed numerals, many previous works have investigated methods to estimate these link parameters, for example link bandwidth estimation [1-3], link buffer size estimation [4-6], and queue length estimation [7-9]. A common assumption among these previous works is that the link bandwidth is constant, which is largely valid for wired networks as the physical link typically has a fixed transmission data rate. However with the rapidly emerging mobile data networks such as 3G [10], HSPA [11], and LTE [12], this assumption is no longer valid.
To illustrate, FIG. 1 plots the measured bandwidth of a production 3G network over a time interval of 10 seconds where there is only a single UDP data flow going from a wired server to a 3G-connected receiver. It is evident that unlike fixed networks, mobile data network can exhibit significant bandwidth fluctuations over a short timescale (as well as over longer timescales, not shown here) even if there is no competing traffic destined to the same receiver. This poses a fundamental challenge to existing link property estimation algorithms as the assumption of fixed link bandwidth no longer holds.
Known algorithms for estimating the link buffer size are max-min [5-6] and loss-pair [6], and queue length estimations, used in TCP Vegas [7], Veno [9] and FAST TCP [8]. Consider the system model depicted in FIG. 2 where a single sender transmits packets via a bottleneck link to a receiver. None of the bottleneck link's parameters are known a priori and the propagation delays are constant. The goal is to estimate the queue length continuously, denoted by qi, and link buffer size, denoted by L, at the sender via observation of the acknowledgement packet arrival times. Table I summarizes the notations used in the following discussions.
TABLE ISymbolDescriptionPd1Propagation delay from sender to the link bufferPd2Propagation delay from link buffer to the receiverPTotal downlink propagation delayUUplink delayqiQueuing delay of the ith packetqmaxMaximum queuing delayniNumber of packets queued-up at the link buffer when ithpacket enters the bufferSPacket sizeLLink buffer size (including the one in service)TTransmission delay of the packetCMeasured link capacitycwndiCongestion window size of the ith packetrttiRound-trip time of the ith packet
Liu and Crovella [6] proposed the max-min method to estimate the link buffer size from the estimated transmission delay and the differences between maximum and minimum round-trip times (RTTs). Claypool et al. [5] further incorporated the max-min method into a measurement tool for use in access networks.
The principle of both max-min [5-6] and loss-pair [6] methods is to use RTT as a mean to measure the link buffer size. Specifically, let P=Pd1+Pd2 be the total downlink propagation delay, T be the transmission delay for one packet, and U be the uplink delay, which are all constant. Next let qi be the queuing delay experienced by packet i at the bottleneck link, and ni be the number of packets already queued-up at the bottleneck link buffer upon its arrival at the queue. Then RTT for packet i, denoted by rtti, can be computed fromrtti=P+T+U+qi  (1)
In a fixed-bandwidth link, the queuing delay of packet i is simply equal to the total time to de-queue the ni packets already in the queue plus the residual transmission time, denoted by rtti, for the packet already in service, i.e.,qi=niT=δ  (2)
Given the link buffer size L, we have ni≦L−1. Also the residual transmission time is bounded by δ≦T. Therefore the maximum queuing delay, denoted by qmax, is given by
                                                                        q                max                            =                            ⁢                              max                ⁢                                  {                                                                                    (                                                  L                          -                          1                                                )                                            ⁢                      T                                        +                    δ                                    }                                                                                                        =                            ⁢              LT                                                          (        3        )            
The minimum queuing delay is simply equal to zero when there is no packet inside the queue upon packet arrival. As the propagation and transmission delays are constant the maximum and minimum RTTs can be computed fromrttmax=P+T+U+qmax  (4)rttmin=P+T+U  (5)
Substituting (3) and (5) into (4), we haverttmax=rttmin+LT  (6)
Similarly, substituting (2) and (5) into (1), yieldsrtti=rttmin+niT+δ  (7)
Rearranging terms in (6), the link buffer size can be determined from [4],
                    L        =                                            rtt              max                        -                          rtt              min                                T                                    (        8        )            
With knowledge of measured link capacity (C) and known packet size (S), the estimated transmission delay (T) can be computed fromT=S/C  (9)and the link buffer size is determined accordingly by
                    L        =                                            (                                                rtt                  max                                -                                  rtt                  min                                            )                        ⁢            C                    S                                    (        10        )            
The max-min method [5-6] is designed for active estimation where the sender sends a series of measurement packets through the bottleneck link at a rate higher than the link bandwidth to induce queue overflow. The receiver returns an acknowledgement (ACK) packet to the sender for every packet received. The sender can then measure the minimum RTT rttmin, maximum RTT rttmax, and link bandwidth C from the ACK packet arrival times. With S known the sender can compute L using (10). The estimation process can also be done by the receiver and the interested readers are referred to the work by Hirabaru [4] for more details.
From (10) it can be seen that the accuracy of the max-min method hinges upon the accuracy in measuring the three parameters, namely rttmax, rttmin, and C. In particular, if there is other cross traffic sharing the same bottleneck link, the RTT measurements will be modulated by the competing flows.
Liu and Crovella [6] tackled this problem in their improved loss-pair method. First, they only capture the RTTs of the two packets just before and after a loss event. This filters out samples not related to buffer overflow at the bottleneck link. Second, they analyze the distribution of the samples to determine their mathematical mode to further filter out noises due to cross traffic. These two techniques improved the accuracy of the loss-pair method.
Queue Length Estimation
There is no presently known measurement tool designed solely for queue length estimation purposes. Unlike link buffer size, which is a physical network property, queue length can vary from time to time depending on many parameters, including offered traffic load, traffic characteristic, link capacity, and so on. Therefore queue length measurement is meaningful only in the context of the actual data flow generated by the transport and/or application protocols.
Some TCP variants do implement algorithms to either implicitly or explicitly estimate the queue length at the bottleneck link for congestion control purpose. One well-known example is TCP Vegas [7] which employs an algorithm to estimate the queue length from the congestion window size and the difference between current and minimum round-trip times (RTTs). Similar algorithms have also been adopted in TCP Veno [9] and FAST TCP [8].
These queue-length estimation algorithms are inherently passive in that only the actual data and ACK packet timings are used for estimating the queue length. No extra measurement packets are generated in the process.
During operation, the TCP sender continuously measures the RTT, denoted by rtti, and records the congestion window size, denoted by cwndi, at the time ACK packet i is received. It then keeps track of the minimum rttmin byrttmin=min{rtti|∀i}  (11)and then computes the estimated queue length, denoted by n′i, from the difference between the expected throughput, i.e., cwndi×rttmin, and the actual measured throughput, i.e., cwndi×rtti, in the last round-trip time [7]:
                              n          i          ′                =                                            cwnd              i                        ⁡                          (                                                rtt                  i                                -                                  rtt                  min                                            )                                            rtt            i                                              (        12        )            
One shortcoming of the Vegas method is that it uses the current congestion window size to estimate the queue length in the previous RTT. In case the congestion window size changes significantly from the last RTT, the estimation accuracy will suffer. This is why TCP Vegas only performs queue length estimation during the congestion avoidance phase where the congestion window size changes slowly.
FAST TCP [8] addressed this shortcoming by keeping track of the past congestion windows, and using the one at the time of the original data transmission instant to compute (12). This improves accuracy and also enables FAST TCP to estimate queue length during both slow-start and congestion avoidance phases.
Using a simulation, the inventors implemented max-min and loss-pair algorithms using UDP as the transport protocol and implemented the Vegas algorithm using TCP CUBIC (default congestion control in Linux) as the transport protocol, and conducted simulations using the network setup in FIG. 2.
In order to assist in evaluation, two performance metrics were defined, called absolute and relative link buffer size estimation errors, denoted by EA and ER respectively, to evaluate the algorithms' performance:
                              E          A                =                              estimated            ⁢                                                  ⁢            link            ⁢                                                  ⁢            buffer            ⁢                                                  ⁢            size                    -                      actual            ⁢                                                  ⁢            link            ⁢                                                  ⁢            buffer            ⁢                                                  ⁢            size                                              (        13        )                                          E          R                =                                            E              A                                      actual              ⁢                                                          ⁢              link              ⁢                                                          ⁢              buffer              ⁢                                                          ⁢              size                                ×          100          ⁢          %                                    (        14        )            
FIG. 3 plots the estimation errors for max-min and loss-pair in active estimation for bottleneck link with buffer size ranging from 100 to 1000 packets. Not surprisingly the algorithms perform well in fixed-bandwidth networks. Their accuracies also improve as link buffer size increases (i.e., due to increases in the denominator of (14)).
Two queue-length estimation algorithms were implemented, namely the Vegas algorithm in TCP Vegas [7] and the FAST algorithm in FAST TCP [8], both using passive estimation. In addition, we also implemented the Vegas algorithm over TCP CUBIC [14]. In this case the TCP flow operates according to TCP CUBIC but the RTTs and congestion window size measurements are then fed into the Vegas algorithm to compute the estimated queue length. This special combination enables us to evaluate the performance of the Vegas estimation algorithm over one of the most widely deployed TCP variant in the Internet.
A relative queue length estimation error QR and absolute queue length estimation error QA were defined as the performance metric:
                              Q          A                =                              estimated            ⁢                                                  ⁢            queue            ⁢                                                  ⁢            length                    -                      actual            ⁢                                                  ⁢            queue            ⁢                                                  ⁢            length                                              (        15        )                                          Q          R                =                                                            estimated                ⁢                                                                  ⁢                queue                ⁢                                                                  ⁢                length                            -                              actual                ⁢                                                                  ⁢                queue                ⁢                                                                  ⁢                length                                                    average              ⁢                                                          ⁢              queue              ⁢                                                          ⁢              length                                ×          100          ⁢          %                                    (        16        )            
FIG. 4 illustrates a comparison of relative queue length estimation errors in different TCP variants for fixed bottleneck link bandwidth. The plots are the estimation errors for the three cases for bottleneck link buffer size ranging from 100 to 1000 packets. There are two anomalies. First, FAST TCP achieved the best accuracy in all cases except the case with a link buffer size of 100 packets where the estimation error jumped to around 60%. This is due to the parameter settings in FAST TCP [8] which specifies the target number of inflight packets to maintain for the data flow. As the default value according to [8] is 100 packets it means FAST TCP will easily overflow the bottleneck link's buffer if the latter's size is close to or below the parameter value. As a result tuning of FAST TCP's parameter will have a significant impact on the performance of queue-length estimation.
Second, the results suggest that the Vegas algorithm when applied to a TCP Vegas flow in fact underperformed the same when applied to a TCP CUBIC flow. This is due to differences between the TCP Vegas and TCP CUBIC's congestion control algorithms. Specifically, TCP Vegas is designed to maintain a small number of packets (around 6 in our simulations) in the bottleneck link buffer. By contrast, TCP CUBIC is far more aggressive and in simulations TCP CUBIC maintained an average queue length at around 90% of link buffer size. Thus the larger denominator in (14) results in lower estimation errors for TCP CUBIC.
If the estimation error is compared in absolute number of packets as shown in FIG. 5 it can be seen that TCP CUBIC did exhibit higher absolute errors when compared to TCP Vegas and FAST TCP, especially for large link buffer sizes. This is because in TCP CUBIC, the congestion window grows faster for larger window sizes. Large link buffer size allows the congestion window to grow larger before buffer overflow occurs, thus causing higher estimation errors in computing (12) where the current congestion window size is used in place of the previous RTT's window size. FAST TCP does not suffer from this problem as it records the sequence of past window sizes and uses the correct one in computing (12), hence maintaining consistent estimation accuracy for a wide range of link buffer sizes.
As herein explained these tools can be used to evaluate the efficacy of the new methods according to the invention.
Citations used herein are as follows:    [1] A. Akella, S. Seshan, and A. Shaikh, “An Empirical Evaluation of Wide-Area Internet Bottlenecks,” Proceedings of the ACM Internet Measurement Conference (IMC), October 2003.    [2] K. Lakshminarayanan and V. Padmanabhan, “Some Findings on the Network Performance of Broadband Hosts,” Proceedings of the ACM Internet Measurement Conference (IMC), October 2003.    [3] V. Ribeiro, R. Riedi, R. Baraniuk, J. Navratil, and L. Cottrell, “pathChirp:Efficient Available Bandwidth Estimation for Network Paths,” PAM, 2003.    [4] M. Hirabaru, “Impact of Bottleneck Queue Size on TCP Protocols and Its Measurement”, IEICE Transactions on Information and Systems, vol. E89-D, No. 1, January 2006, pp. 132-138.    [5] M. Claypool, R. Kinicki, M. Li, J. Nichols, and H. Wu, “Inferring Queue Sizes in Access Networks by Active Measurement”, PAM, 2004.    [6] J. Liu and M. Crovella, “Using Loss Pairs to Discover Network Properties”, ACM SIGCOMM Workshop on Internet Measurement, pp. 127-138, 2001.    [7] L. S. Brakmo, S. W. O'Malley, and L. L. Peterson, “TCP Vegas: New techniques for congestion detection and avoidance,” Proceedings of the SIGCOMM '94, London, U.K., October 1994, pp. 24-35    [8] S. Hegde, D. Lapsley, B. Wydrowski, J. Lindheim, D. Wei, C. Jin, S. Low, and H. Newman, “FAST TCP in High Speed Networks: An Experimental Study,” Proceeding of GridNets, October 2004.    [9] C. P. Fu, and S. C. Liew, “TCP Veno: TCP enhancement for wireless access networks,” IEEE Journal of Selected Areas in Communications, vol. 21 no. 2, February 2003.    [10] V. K. Garg, Wireless Network Evolution: 2G to 3G, Prentice Hall PTR, Upper Saddle River, N.J., USA, 2001.    [11] E. Dahiman, S. Parkvall, J. Skold, P. Beming, 3G Evolution: HSPA and LTE for Mobile Broadband, 2nd ed., Academic Press, 2008.    [12] D. Astely, E. Dahlman, A. Furuskar, Y. Jading, M. Lindstrom, and S. Parkvall, “LTE: The Evolution of Mobile Broadband”, IEEE Communications Magazine, vol. 47(4), April 2009, pp. 44-51.    [13] K. Liu and J. Y. B. Lee, “Mobile Accelerator: A New Approach to Improve TCP Performance in Mobile Data Networks,” Proc. 7th IEEE International Wireless Communications and Mobile Computing Conference (IWCMC 2011), Istanbul, Turkey, Jul. 5-8, 2011.    [14] A. B. Downey, “Using pathchar to estimate internet link characteristics,” Proceedings of ACM SIGCOMM 1999, August 1999.    [15] S. Ha, I. Rhee and L. Xu, “CUBIC: A New TCP-Friendly High-Speed TCP Variant,” International Workshop on Protocols for Fast and Long Distance Networks, 2005.    [16] NS2, Network Simulator, http://www.isi.edu/nsnam/ns/.    [17] S. Floyd, J. Mandavi, M. Mathis, and M. Podolsky, An extension to the selective acknowledgement (SACK) option for TCP, Request for Comments 2883, 2000.    [18] FAST TCP ns2 module, http://www.cubinlab.ee.unimelb.edu.au/ns2FASTtcp/    [19] O. Ait Hellal, E. Altman “Problems in TCP Vegas and TCP Reno”, DNAC Cong. (De Nouvelles Architectures pourles Communications), UVSQ, Paris, Dec. 3-5, 1996.    [20 S. Mascolo, C. Casetti, M. Geria, M. Y. Sanadidi and R. Wang, “TCP Westwood: Bandwidth Estimation for Enhanced Transport over Wireless Links,” in Proceedings of ACM SIGMOBILE, July 2001.    [21] Apache, http://www.apache.org/    [22] Wget, http://gnuwin32.sourceforge.net/packages/wget.htm    [23] Wireshark, http://www.wireshark.org/